#include "testBSTRange.hpp"

int main(int argc, char const *argv[])
{
    auto *pbst = new BinarySearchTree<int>();

    std::cout
        << "1. Accuracy Test for Searching Range Algorithm Based on BinarySearchTree:"
        << std::endl;
    RandomInitializeBST(pbst, 10);
    std::cout
        << "# Construct a random BST, ranging from 1 to 10;"
        << std::endl;
    testBSTRange(pbst, 1, 5, true);
    testBSTRange(pbst, -15, 57, true);
    testBSTRange(pbst, 5, 5, true);
    testBSTRange(pbst, 10, 9, true);

    std::cout
        << "2. Time Test for Searching Range Algorithm Based on BinarySearchTree:"
        << std::endl;

    const int TotalRepeatTimes = 1;
    std::cout << "# Repeat " << TotalRepeatTimes << " times to obtain an average time\n";
    for (int K : {2})
    {
        std::cout << "2.1 Fix K = " << K << ":\n";
        for (int N : {2000, 4000, 8000, 16000, 32000, 64000})
        {
            double averge_time = 0;
            for (int repeat = 0; repeat < TotalRepeatTimes; repeat++)
            {
                const int inf = RandomInt(N - K, repeat)+1;
                RandomInitializeBST(pbst, N, repeat);
                averge_time += (testBSTRange(pbst, inf, inf + K)) / TotalRepeatTimes;
            }
            std::cout << "N = " << N << " takes " << averge_time << "s in average.\n";
        }
    }

    for (int N : {256000})
    {
        std::cout << "2.2 Fix N = " << N << ":\n";
        for (int K : {2000, 4000, 8000, 16000, 32000, 64000})
        {
            double averge_time = 0;
            for (int repeat = 0; repeat < TotalRepeatTimes; repeat++)
            {
                const int inf = RandomInt(N - K, repeat);
                RandomInitializeBST(pbst, N, repeat);
                averge_time += (testBSTRange(pbst, inf, inf + K)) / TotalRepeatTimes;
            }
            std::cout << "K = " << K << " takes " << averge_time << "s in average.\n";
        }
    }

    std::cout << "2.3 Fix K = N/2:\n";
    for (int N : {4000, 8000, 16000, 32000, 64000})
    {
        int K = N / 2;
        double averge_time = 0;
        for (int repeat = 0; repeat < TotalRepeatTimes; repeat++)
        {
            const int inf = RandomInt(N - K, repeat);
            RandomInitializeBST(pbst, N, repeat);
            averge_time += (testBSTRange(pbst, inf, inf + K)) / TotalRepeatTimes;
        }
        std::cout << "N,K = " << N << "," << K << " takes " << averge_time << "s in average.\n";
    }
    delete pbst;
    return 0;
}
